Machine-independent "and" and "or" parallel execution of logic programs

Parallel machines are becoming increasingly cheap and more easily available. Commercial companies have already announced MIMD machines with more than 8000 processors. This prompts three questions: Should the programmer have to rewrite existing software for each new machine that comes along? Should it be necessary for the programmer to have intimate knowledge of the target machine in order to program it efficiently? Is it necessary for the programmer to identify the parallelism in programs explicitly?Our thesis is that the answer is 'no' on all three counts. We demonstrate that it is possible for users to write parallel programs in a machine independent manner. We address this problem at two levels. We first describe the design and implementation of a parallel run time support system called the Chare kernel that provides a uniform interface to the programmer on the class of MIMD machines. This support system makes it possible for programmers to write machine independent programs efficiently. We choose the logic programming paradigm where a high level specification of the problem is possible and it is amenable to the implicit detection of parallelism. We have designed and implemented a compiler that exploits AND and OR parallelism in logic programs. We have developed an emulator for abstract machine code generated by our compiler as an application on the Chare kernel which runs without modification on shared memory and nonshared memory machines alike.This thesis discusses addresses algorithmic issues relating to the design and implementation of an efficient parallel Prolog compiler on both shared and nonshared machines. This work differs significantly from most other related research, in part due to their dependence on a global memory address space. This work is the first to demonstrate that nonshared machines like the Intel and NCUBE hypercubes can be exploited effectively for the parallel execution of logic programs. It also provides a convincing demonstration of machine independent parallel programming.U of I OnlyETDs are only available to UIUC Users without author permissio